# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pos1,pos2=head,head ###快慢指针将链表一分为二
        while pos2:
            pos2=pos2.next
            if not pos2:break
            pos2=pos2.next
            if not pos2:break
            pos1=pos1.next
        start=pos1.next     ##另外一半链表
        pos1.next=None      ####断链
        l1=self.sortList(head)
        l2=self.sortList(start)
        root=ListNode(-1)   ######增加一个头节点方便返回
        cur=root
        while l1 and l2:     ######对两个链表进行归并
            if l1.val<l2.val:
                cur.next=l1
                l1=l1.next
            else:
                cur.next=l2
                l2=l2.next
            cur=cur.next
        if l1:cur.next=l1    #剩下的合并
        if l2:cur.next=l2
        return root.next